package de.unikoblenz.west.csxpoi.server;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.openrdf.query.MalformedQueryException;
import org.openrdf.query.QueryEvaluationException;
import org.openrdf.repository.RepositoryConnection;
import org.openrdf.repository.RepositoryException;

/**
 * Implements the DBSCAN clustering algorithm.
 */
public class Clustering {
	/**
	 * flag for clustering events
	 */
	public static Similarity  mSimilarity;
	/**
	 * the minimal size of a neighborhood
	 */
	private static final int MU = 2;

	/**
	 * the minimal similarity for members of a neighborhood
	 */
	private static final double EPS = 0.65;

	/**
	 * the set of all clusters
	 */
	private static Set<Cluster> mClusters = new HashSet<Cluster>();

	/**
	 * the set of all POIs
	 */
	private static List<PoiWrapper> mPois = new ArrayList<PoiWrapper>();

	/**
	 * Starts the DBSCAN clustering algorithm on the provided list of POIs and
	 * returns a set of clusters.
	 * 
	 * @param pois
	 *            the POIs to cluster
	 * @param connection
	 *            a repository connection
	 * @return a set of clusters
	 * @throws RepositoryException
	 * @throws MalformedQueryException
	 * @throws QueryEvaluationException
	 */
	public static Set<Cluster> dbscan(List<PoiWrapper> pois,
			RepositoryConnection connection, Similarity similarity)
			throws RepositoryException, MalformedQueryException,
			QueryEvaluationException {
		mSimilarity = similarity;
		mClusters.clear();
		mPois = pois;

		for (PoiWrapper poi : mPois) {
			expand(poi);
		}

		return mClusters;
	}

	/**
	 * Expands a cluster around a POI with its neighborhood by calling itself
	 * recursively.
	 * 
	 * @param poi
	 *            the POI to expand
	 */
	private static void expand(PoiWrapper poi) {

		Cluster cluster = poi.getCluster();
		if (cluster.equals(Cluster.NONE) || cluster.equals(Cluster.NOISE)) {
			cluster = new Cluster();
		}

		List<PoiWrapper> neighborhood = neighborhood(poi);

		if (neighborhood.size() < MU) {
			if (poi.getCluster().equals(Cluster.NONE)) {
				poi.addToCluster(Cluster.NOISE);
			}
		} else {
			poi.addToCluster(cluster);
			List<PoiWrapper> newMembers = new ArrayList<PoiWrapper>();
			for (PoiWrapper neighbor : neighborhood) {
				if (neighbor.getCluster().equals(Cluster.NONE)
						|| neighbor.getCluster().equals(Cluster.NOISE)) {
					neighbor.addToCluster(cluster);
					newMembers.add(neighbor);
				}
			}
			for (PoiWrapper newMember : newMembers) {
				// TODO: replace recursive implementation
				expand(newMember); 
			}
			mClusters.add(cluster);
		}
	}

	/**
	 * Determines the neighborhood of a POI.
	 * 
	 * @param poi
	 *            the POI for which to determine the neighborhood
	 * @return the list of POIs constituting the neighborhood of poi
	 */
	private static List<PoiWrapper> neighborhood(PoiWrapper poi) {

		// TODO: only consider POIs in the vicinity to improve performance
		List<PoiWrapper> neighborhood = new ArrayList<PoiWrapper>();

		for (PoiWrapper neighbor : mPois) {
			try {
				if (mSimilarity.similarity(neighbor, poi) > EPS) {
					neighborhood.add(neighbor);
				}
			} catch (SimilarityException e) {
				// not comparable
			}
		}

		return neighborhood;
	}

}
